'''
Created on 2013-6-13

@author: zouliping
'''
import time

count = 0
buildShiftTime = 0

def get_pre_suf_len(pattern):
	jump = [0]
	m = len(pattern)
	tmp = 0
	for i in range(1,m):
		while tmp > 0 and pattern[tmp] != pattern[i]: 
			tmp = jump[tmp - 1]
		if pattern[tmp] == pattern[i]:
			tmp += 1
		jump.append(tmp)
	return jump

def KnuthMorrisPratt(text, pattern, debug = False):
	global count, buildShiftTime
	start = time.time()
	jump = get_pre_suf_len(pattern)
	if debug:
		print jump
	end = time.time()
	buildShiftTime = end - start
	m = len(pattern)
	n = len(text)
	tmp = 0
	for i in range(n):
		while tmp > 0 and pattern[tmp] != text[i]:
			tmp = jump[tmp - 1]
			if debug:
				print text
				print ' ' * (i - tmp - 1), pattern
			count += 1
		if pattern[tmp] == text[i]:
			tmp += 1
		else:
			if debug:
				print text
				print ' ' * (i - jump[tmp -1]), pattern
			count += 1
		if tmp == m:
			# print 'match at', i - m + 1,'to', i
			tmp -= jump[m - 1]
			return i - m + 1
	return -1

def main():
	text = 'bbc abcdab abcdabcdabde'
	pattern = 'abcdabd'
	offset = KnuthMorrisPratt(text, pattern, True)
	if offset == -1:
		print 'lost'
	else:
		print 'hit at : ', offset

if __name__ == '__main__':
	main()
